//链表判环，并找到入口

//方法一：哈希表
//遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。并返回入口起点
//时间复杂度O(n)，空间复杂度O(n)
/**
 *  Definition for singly-linked list.
 *  struct ListNode {
 *       int val;
 *       ListNode *next;
 *       ListNode(int x) : val(x), next(NULL) {}
 *  };
 *        */
class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            std::unordered_set<ListNode*> uset;
            while(head != nullptr)
            {
                if(uset.count(head))  //head存在，则输出
                    return head;
                uset.insert(head);
                head = head->next;
            }
            return nullptr;
        }
};

//方法二：快慢指针
//假设从 头结点到环形入口节点 的节点数为 X
//环形入口节点到 fast指针与slow指针相遇节点 节点数为 Y
//从相遇节点 再到环形入口节点 节点数为 Z
//slow指针走过的节点数为: x + y。 fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，(y+z)为 一圈内节点的个数
//因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2，即(x + y) * 2 = x + y + n (y + z)，两边消掉一个（x+y）: x + y = n (y + z)
//因为我们要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。x = n (y + z) - y
//x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针
//当 n为1的时候，公式就化解为 x = z
//从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点
//也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
//让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
//n>1的情况一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
//时间复杂度：O(n)，空间复杂度：O(1)
class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            ListNode* fast = head;
            ListNode* slow = head;
            while(fast != nullptr && fast->next != nullptr)
            {
                fast = fast->next->next;
                slow = slow->next;
                // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
                if(fast == slow)
                {
                    ListNode* index1 = head;
                    ListNode* index2 = fast;
                    while(index1 != index2)
                    {
                        index1 = index1->next;
                        index2 = index2->next;
                    }
                    return index1;  // 返回环的入口
                }
            } 
            return nullptr;
        }
};
